package newcoder_exp.justPractise;

import java.util.Arrays;

import org.junit.Test;

import linked.ListNode;
import utils.ArrayGenerator;

public class NC70 {

    @Test
    public void test() {
        Solution s = new Solution();
        for (int i = 0; i < 100; i++) {
            int[] nums = ArrayGenerator.getArray(100, 20);
            ListNode head = ListNode.newListNodeFromArray(nums);
            ListNode res = s.sortInList(head);
            String r1 = res.toString();
            Arrays.sort(nums);
            String r2 = Arrays.toString(nums);
            System.out.println(r1.equals(r2));
        }
        // System.out.println(res);
    }
    
    public class Solution {
        /**
            链表归并排序
        */
        public ListNode sortInList (ListNode head) {
            if (head == null || head.next == null) return head;
            return mergeSort(head, null);
        }

        public ListNode mergeSort(ListNode head, ListNode end) {
            if (head == end || head.next == end) return head;
            ListNode mid = findMid(head, end);
            ListNode left = mergeSort(head, null);
            ListNode right = mergeSort(mid, null);
            return merge(left, right);
        }

        public ListNode findMid(ListNode head, ListNode end) {
            //从当前节点开始，找到从此到end前一个节点这一段的中点
            if (head == end || head.next == end) return head;
            ListNode fast = head, slow = head, pre = null;
            while (fast != end && fast.next != end) {
                fast = fast.next.next;
                pre = slow;
                slow = slow.next;
            }
            pre.next = null;
            //奇偶情形：
            if (fast == end) {
                //fast == end, 长度为偶数个，此时s正好停留在中间靠右地位置
                //slow适合作为右半边的起始点，以及上半部分的end
                return slow;
            } else {
                //fast.next == end
                //长度为奇数个，s为中间位置
                //划分：head ~ slow前一个， slow ~ end前一个
                return slow;
            }
            //上面两种，都需要slow作为下一个位置的起点，并且作为上半边的划分end
        }

        //对两段有序链表进行归并
        public ListNode merge(ListNode p, ListNode q) {
            ListNode res = new ListNode(0), result = res;
            while (p != null && q != null) {
                if (p.val <= q.val) {
                    res.next = p;
                    p = p.next;
                } else {
                    res.next = q;
                    q = q.next;
                }
                res = res.next;
            }
            if (p == null) p = q;
            res.next = p;
            return result.next;
        }
    }
}
